﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//链表面试题：

//题目一：
//1. 删除链表中等于给定值 val 的所有结点
//给你一个链表的头节点head和一个整数 val 请你删除链表中所有满足Node.val==val的节点
//并返回的头节点


//方法一：直接遍历比较然后删除
 struct ListNode 
 {
     int val;
     struct ListNode *next;
 };
struct ListNode* removeElements(struct ListNode* head, int val) 
{
	struct ListNode* pre = NULL;
	struct ListNode* cur = head;
	while (cur!= NULL)
	{
		if (cur->val != val)
		{
			pre = cur;
			cur = cur->next;
		}
		else
		{
			//如果头节点就要进行删除的话
			if (pre == NULL)
			{
				head = cur->next;
				free(cur);
				cur = head;
			}
			else
			{
				pre->next = cur->next;
				free(cur);
				cur = pre->next;
			}
			
		}
	}
	return head;
}

//方法二：把不是val的值的元素，插到新链表里面
struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
	struct ListNode* newnode = NULL;
	struct ListNode* tail = NULL;
	struct ListNode* cur = head;
	while (cur != NULL)
	{
		if (cur->val != val)
		{
			//尾插
			if (tail == NULL)
			{
				tail = newnode = cur;
			}
			else
			{
				tail->next = cur;
				tail = tail->next;
			}
			cur = cur->next;
		}
		else
		{
			struct ListNode* tmp = cur->next;
			free(cur);
			cur = tmp;
		}
	}
	if (tail != NULL)
	{
		tail->next = NULL;
	}
	return newnode;
}



//题目二：
//2. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则
//返回第二个中间结点
//给你单链表的头结点 head ，请你找出并返回链表的中间结点。
//如果有两个中间结点，则返回第二个中间结点。


//思路一：进行依次遍历，然后求出该链表的元素个数
//思路二：用快慢指针法，快指针依次走两步，慢指针依次走一步，快指针走到结尾，满指针就是中间位置
 

//快慢指针
struct ListNode 
 {
     int val;
     struct ListNode *next;
 };
struct ListNode* middleNode(struct ListNode* head) 
{
	struct ListNode* slow;
	struct ListNode* fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}


//题目三：
//3.输入一个链表，输出该链表中倒数第k个结点。

//方法一：先遍历一遍这个链表，计算出元素的个数n，那么就直接找正数第n-k个就是倒数第k个
//方法二，使用快慢指针，快指针先走k-1或者k步，然后fast和slow两个指针同时走

//快慢指针法
struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* FindKthTotail(struct ListNode* plisthead,int k)
{
	if (plisthead == NULL)
	{
		return NULL;
	}
	struct ListNode* fast;
	struct ListNode* slow;
	slow = fast = plisthead;
	//让快指针fast先走k步
	while (k--)
	{
		if (fast == NULL)
		{
			return NULL;
		}
		fast = fast->next;

	}
	while (fast)
	{
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}



//题目四：
//4. 反转一个单链表。
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

//思路1：直接调换指针的指向，让这个链表指向反过来，直接创建三个指针，n1、n2改指向，n3保存下一个的位置
//思路2：将每一个数都头插到新链表

//思路一：三个指针
 struct ListNode 
 {
     int val;
     struct ListNode *next;
 };
 
struct ListNode* reverseList(struct ListNode* head) 
{
	if (head == NULL)
	{
		return NULL;
	}
	struct ListNode* n1;
	struct ListNode* n2;
	struct ListNode* n3;
	n1 = NULL;
	n2 = head;
	n3 = head->next;
	while (n2!=NULL)
	{
		n2->next = n1;
		//迭代
		n1 = n2;
		n2 = n3;
		if(n3!=NULL)
		n3 = n3->next;
	}
	return n1;
}

//思路2：头插到新链表
struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* cur=head;
	struct ListNode* newhead=NULL;
	while (cur)
	{
		struct ListNode* next = cur->next;
		//头插
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	return newhead;
}


//题目五：
//5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有
//结点组成的
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

//思路：依次比较，取小的数进行尾插


struct ListNode 
{
	int val;
	struct ListNode* next;
	
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}
	struct ListNode* cur1 = list1;
	struct ListNode* cur2 = list2;
	struct ListNode* head = NULL;
	struct ListNode* tail = NULL;
	while (cur1 && cur2)
	{
		if (cur1->val < cur2->val)
		{
			if (head == NULL)
			{
				head = tail = cur1;
			}
			else
			{
				tail->next = cur1;
				tail = tail->next;
			}
			cur1 = cur1->next;
		}
		else
		{
			if (head == NULL)
			{
				head = tail = cur2;
			}
			else
			{
				tail->next = cur2;
				tail = tail->next;
			}
			cur2 = cur2->next;
		}
	}
	if (cur1)
	{
		tail->next = cur1;
	}
	if (cur2)
	{
		tail->next = cur2;
	}
	return head;
}



//题目六：
//6.链表的分割，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
//现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前
//且不能改变原来的数据顺序，返回重新排列后的链表的头指针。


//思路：把小于x的尾插到一个链表，把大于x的尾插到另一个链表，然后在把他们链接起来
//这里最好使用哨兵位的头节点，不然不好处理空的问题



 struct ListNode 
 {
      int val;
      struct ListNode *next;
 };
 
struct ListNode* partition(struct ListNode* pHead, int x)
{
	//使用哨兵位
	struct ListNode* gGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* lGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* gTail = gGuard;
	struct ListNode* lTail = lGuard;
	gTail->next = NULL;
	lTail->next = NULL;
	struct ListNode* cur = head;
	while (cur)
	{
		if (cur->val < x)
		{
			lTail->next = cur;
			lTail = lTail->next;
		}
		else
		{
			gTail->next = cur;
			gTail = gTail->next;
		}
		cur = cur->next;
	}
	lTail->next = gGuard->next;
	gTail->next = NULL;

	pHead = lGuard->next;
	free(gGuard);
	free(lGuard);
	return pHead;

}



//题目七：
//链表的回文结构
//对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构
//给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900

//思路1:找到中间节点，然后从中间节点开始，对后半段开始逆置，然后前半段和后半段进行比较
//思路2：创建一个数组，把所有数字赋值进去，然后逆向的遍历数组


//思路1：
struct ListNode 
{
	int val;
	struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
	struct ListNode* slow;
	struct ListNode* fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	struct ListNode* n1;
	struct ListNode* n2;
	struct ListNode* n3;
	n1 = NULL;
	n2 = head;
	n3 = head->next;
	while (n2 != NULL)
	{
		n2->next = n1;
		//迭代
		n1 = n2;
		n2 = n3;
		if (n3 != NULL)
			n3 = n3->next;
	}
	return n1;
}
bool isPalindrome(struct ListNode* head)
{
	
	struct ListNode* middle = middleNode(head);
	struct ListNode* remiddle = reverseList(head);
	
	while (head && remiddle)
	{
		if (head->next != remiddle->next)
		{
			return false;
		}
		head = head->next;
		remiddle = remiddle->next;
	}
	return true;
}

//思路2：
bool isPalindrome(struct ListNode* head)
{

	int array[50001];
	int num = 0;
	while (head)
	{
		array[num++] = head->val;
		head = head->next;
	}
	for (int i = 0, j = num - 1; i < j; i++, j--)
	{
		if (array[i] != array[j])
		{
			return false;
		}
	}
	return true;
}



//题目八：
//8.输入两个链表，找出它们的第一个公共结点
//给你两个单链表的头节点headA和headB
//请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null


//思路1：把链表1里面的每个元素依次与链表2的每个元素比较，然后那个相同的就是相交的地方
//思路2：先求两个链表的长度，，然后在让长的那个链表走差距步，然后第一个地址相同的地方就是相交的地方


struct ListNode 
{
	int val;
	struct ListNode* next;
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
	struct ListNode* tailA = headA, * tailB = headB;
	int lenA = 1, lenB = 1;
	while (tailA->next)
	{
		tailA = tailA->next;
		lenA++;
	}
	while (tailB->next)
	{
		tailB = tailB->next;
		lenB++;
	}
	//如果尾节点的地址不相同，那么他们一定不相交
	if (tailA != tailB)
	{
		return NULL;
	}
	int gap = abs(lenA - lenB);
	struct ListNode* longlist = headA, *shortlist = headB;
	if (lenA < lenB)
	{
		longlist = headB;
		shortlist = headA;
	}

	while (gap--)
	{
		longlist = longlist->next;
	}
	while (longlist != shortlist)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}
	return longlist;
}


//题目九：
//9. 给定一个链表，判断链表中是否有环。
//给你一个链表的头节点 head ，判断链表中是否有环。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
//为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）
//注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
//如果链表中存在环，则返回 true。否则，返回 false

//思路：快慢指针法，用快指针走两步，慢指针走一步，那么一旦有环，那么他们一定会相遇
struct ListNode 
{
	int val;
	struct ListNode* next;
};
bool hasCycle(struct ListNode* head) 
{
	struct ListNode* slow, * fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow)
		{
			return true;
		}
	}
	return false;
}

//两个问题：
//1.为什么使用快慢指针？他们为什么会相遇，一定会相遇吗？会不会错过？
//2.那满指针每次走一步，快指针n步（n>2）可以吗？
//画图分析参考png








